Search results for " random walk"

A Hierarchical Learning Scheme for Solving the Stochastic Point Location Problem

2012

Published version of a chapter in the book: Advanced Research in Applied Artificial Intelligence. Also available from the publisher at: http://dx.doi.org/10.1007/978-3-642-31087-4_78 This paper deals with the Stochastic-Point Location (SPL) problem. It presents a solution which is novel in both philosophy and strategy to all the reported related learning algorithms. The SPL problem concerns the task of a Learning Mechanism attempting to locate a point on a line. The mechanism interacts with a random environment which essentially informs it, possibly erroneously, if the unknown parameter is on the left or the right of a given point which also is the current guess. The first pioneering work […

A novel strategy for solving the stochastic point location problem using a hierarchical searching scheme

2014

Stochastic point location (SPL) deals with the problem of a learning mechanism (LM) determining the optimal point on the line when the only input it receives are stochastic signals about the direction in which it should move. One can differentiate the SPL from the traditional class of optimization problems by the fact that the former considers the case where the directional information, for example, as inferred from an Oracle (which possibly computes the derivatives), suffices to achieve the optimization-without actually explicitly computing any derivatives. The SPL can be described in terms of a LM (algorithm) attempting to locate a point on a line. The LM interacts with a random environme…

Quantum Random Walks – New Method for Designing Quantum Algorithms

2008

Quantum walks are quantum counterparts of random walks. In the last 5 years, they have become one of main methods of designing quantum algorithms. Quantum walk based algorithms include element distinctness, spatial search, quantum speedup of Markov chains, evaluation of Boolean formulas and search on "glued trees" graph. In this talk, I will describe the quantum walk method for designing search algorithms and show several of its applications.

Quadratic speedup for finding marked vertices by quantum walks

2020

A quantum walk algorithm can detect the presence of a marked vertex on a graph quadratically faster than the corresponding random walk algorithm (Szegedy, FOCS 2004). However, quantum algorithms that actually find a marked element quadratically faster than a classical random walk were only known for the special case when the marked set consists of just a single vertex, or in the case of some specific graphs. We present a new quantum algorithm for finding a marked vertex in any graph, with any set of marked vertices, that is (up to a log factor) quadratically faster than the corresponding classical random walk.

Avoiding Boundary Effects in Wang-Landau Sampling

2003

A simple modification of the ``Wang-Landau sampling'' algorithm removes the systematic error that occurs at the boundary of the range of energy over which the random walk takes place in the original algorithm.

Poisson convergence on continuous time branching random walks and multistage carcinogenesis.

1982

A theorem for Poisson convergence on realizations of two-dimensional Branching Random Walks with an underlying continuous time Markov Branching Process is proved. This result can be used to gain an approximation for the number of cells having sustained a certain deficiency after a long time in multistage carcinogenesis.

Scaling and data collapse for the mean exit time of asset prices

2005

We study theoretical and empirical aspects of the mean exit time of financial time series. The theoretical modeling is done within the framework of continuous time random walk. We empirically verify that the mean exit time follows a quadratic scaling law and it has associated a pre-factor which is specific to the analyzed stock. We perform a series of statistical tests to determine which kind of correlation are responsible for this specificity. The main contribution is associated with the autocorrelation property of stock returns. We introduce and solve analytically both a two-state and a three-state Markov chain models. The analytical results obtained with the two-state Markov chain model …

One-Dimensional Diffusion

2009

Quantum Search with Multiple Walk Steps per Oracle Query

2015

We identify a key difference between quantum search by discrete- and continuous-time quantum walks: a discrete-time walk typically performs one walk step per oracle query, whereas a continuous-time walk can effectively perform multiple walk steps per query while only counting query time. As a result, we show that continuous-time quantum walks can outperform their discrete-time counterparts, even though both achieve quadratic speedups over their corresponding classical random walks. To provide greater equity, we allow the discrete-time quantum walk to also take multiple walk steps per oracle query while only counting queries. Then it matches the continuous-time algorithm's runtime, but such …

Geometry and time scale of the rotational dynamics in supercooled toluene

1998

Multidimensional deuteron NMR provides powerful tools for studying molecular reorientation in supercooled liquids. We present results on selectively deuterated toluene-${d}_{5},$ which may be one of the molecularly most simple van der Waals glass formers. From two-time correlation functions the time scale of reorientation was obtained slightly above the calorimetric glass transition temperature. The applied stimulated echo method provides a geometry parameter that, in analogy to $q$-dependent scattering experiments, allows one to investigate the geometry of the elementary rotational process. Continuous time random walk computer simulations were used for the interpretation of the data. It is…